package zuoshen_video2.sort;

import java.util.*;

import org.junit.Test;

import utils.ArrayGenerator;

public class KielSort {
    
    // 1.使用有序集合的方式
    //[不能使用List类型的数组，且外层的list没有add之前不能通过set(i, new List)的形式，因此采用Map代替外层的数组]
    public void kielSort1(int[] nums) {
        //数位桶
        Map<Integer, List<Integer>> bucket = new HashMap<>();
        
        int d = maxDigit(nums);
        for (int i = 1; i <= d; i++) {
            //当前遍历到的数位为i
            for (int j = 0; j < 10; j++) {
                bucket.put(j, new ArrayList<>()); //将桶位初始化为空，替换老桶位
            }
            for (int j = 0; j < nums.length; j++) {
                int n = curDigit(nums[j], i); 
                bucket.get(n).add(nums[j]);
            }
            int idx = 0;
            for (int j = 0; j < 10; j++) {
                //将桶中元素复制回原数组
                List<Integer> cur = bucket.get(j);
                for (int c: cur) {
                    nums[idx++] = c;
                }
            }
        }
    }

    // 2.使用位桶的方式
    public void kielSort2(int[] nums) {
        int d = maxDigit(nums), len = nums.length;

        for (int i = 1; i <= d; i++) {
            //数位i

            int[] count = new int[10];
            //计算频次
            for (int j = 0; j < len; j++) {
                count[curDigit(nums[j], i)]++;
            }

            //转为前n项和
            for (int j = 1; j < 10; j++) count[j] += count[j - 1];

            int[] help = new int[len];
            //count[curD]就是这个数这一轮应该待在help中的位置，即前n项和最后一个位置-1，并将count[curD]--
            for (int j = len - 1; j >= 0; j--) {
                help[--count[curDigit(nums[j], i)]] = nums[j];
            }

            //help拷贝回原数组
            for (int j = 0; j < len; j++) nums[j] = help[j];
        }
    }

    // 共用方法，求最大数位，O(N*d)
    public int maxDigit(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int count = 0, n = nums[i];
            while (n != 0) {
                n /= 10;
                count++;
            }
            res = Math.max(count, res);
        }
        return res;
    }

    //共用方法：求当前需要的数位
    public int curDigit(int n, int d) {
        n /= (int)Math.pow(10, d - 1);
        return n % 10;
    }

    @Test
    public void test() {
        int[] nums = {123, 92, 561, 34, 81};
        nums = ArrayGenerator.getArray(1000, 1000);
        kielSort2(nums);
        System.out.println(Arrays.toString(nums));
    }
}
